package com.berchen.算法.普利姆算法;

import java.util.Arrays;

/**
 * 普利姆算法
 * 最小生成树 解决问题
 * 有多个村庄 村庄之间有路通 每条路的距离都固定
 * 现在需要修路 保证 每个村庄都能连通 并且保证修的路的长度为最短
 *
 * 通过最小生成树来解决该问题
 * AB 5
 * AC 7
 * AG 2
 * BG 3
 * BD 9
 * DF 4
 * FE 5
 * FG 6
 * EG 4
 * CE 8
 *
 * 上面就是图
 * 思路：
 * 先以A为起点  找到与A连通的所有变  取最小距离
 * AB 5
 * AC 7
 * AG 2
 * =>> 得到 AG=2
 *
 * 以A G 为起点 找到与A G 连通的顶点的边（该顶点是没有被找到的顶点）
 * AB 5
 * AC 7
 * GE 4
 * GF 6
 * GB 3
 * =>> 得到 GB=3
 *
 * 以 A G B 为起点 找到A G B 连通的顶点的边
 * AC 7
 * GE 4
 * GF 6
 * BD 9
 * =>> 得到 GE =4
 *
 * 以 A G B E 为起点 找到  A G B E 连通的顶点的边
 * AC 7
 * GF 6
 * BD 9
 * EF 5
 * EC 8
 * =>> 得到EF =5
 *
 * 以 A G B E F 为起点 找到 A G B E F 连通的顶点的边
 * AC 7
 * BD 9
 * EC 8
 * FD 4
 * =>> 得到 FD =4
 *
 * 以 A G B E F D 为起点 找到 A G B E F D 连通的顶点的边
 * AC 7
 * BD 9
 * EC 8
 * =>> 得到 AC =7
 *
 * 至此我们找到了最小生成树 的边
 * AG GB GE EF FD AC
 *
 */
public class Prim {
    public static void main(String[] args) {
        char [] data={'A','B','C','D','E','F','G',};
        int verxs=data.length;
        int[][] weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}
        };
        Graph graph = new Graph(verxs);
        MinTree minTree=new MinTree();
        minTree.createGraph(graph,verxs,data,weight);
        minTree.showGraph(graph);

        // 测试普利姆算法 随便从哪个点作为开头去找都可以（只要不越界）
        minTree.prim(graph,1);
    }
}

/**
 * 最小生成树
 */
class MinTree{

    // 编写普利姆算法 生成最小生成树
    /**
     *
     * @param graph
     * @param v 从图的第几个顶点开始生成最小生成树
     */
    public void prim(Graph graph,int v ){

        // 用来保存顶点是否被访问过
        int [] visited=new int[graph.verxs];

        // 把当前节点标记为已访问
        visited[v]=1;
        // 用h1 h2 记录两个顶点的下标
        int h1=-1;
        int h2=-1;
        // 将minWeight 初始化一个大值 后面遍历过程中，会被替换 只要有一个边的权比这个小 就会替换
        int minWeight=10000;
        for(int k=1;k<graph.verxs;k++){ // graph.verxs 个顶点 普利姆算法后 有graph.verxs-1条边

            // 这个是确定每一次生成的子图，和那个节点的距离最近
            for(int i =0;i<graph.verxs;i++){    // i 节点 表示被访问过的节点
                for(int j =0;j<graph.verxs;j++){    // j 节点 表示还没有访问过的节点
                    if(visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){
                        // 替换minWeight (寻找已经访问过的节点和未访问过的节点间的权值最小的边)
                        minWeight=graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            // 找到一条边是最小
            System.out.println("边 < "+graph.data[h1]+" , "+graph.data[h2]+" > 权值 = "+ minWeight);
            // 将当前找到的节点 标记为已经访问
            visited[h2]=1;
            // 重新设置为最大值
            minWeight=10000;
        }
    }

    /**
     * 创建图的方法
     * @param graph 图对象
     * @param verxs 图的节点个数
     * @param data  图的节点的值
     * @param weight 图的边的权重
     */
    public void createGraph(Graph graph,int verxs,char[] data,int[][] weight){
        int i,j;
        for(i=0;i<verxs;i++){
            graph.data[i]=data[i];
            for(j=0;j<verxs;j++){
                graph.weight[i][j]=weight[i][j];
            }
        }
    }

    /**
     * 显示图的临界矩阵
     * @param graph
     */
    public void showGraph(Graph graph){
        for (int[] link:graph.weight){
            System.out.println(Arrays.toString(link));
        }
    }
}
/**
 * 图
 */
class Graph{
    int verxs;  // 图的节点个数
    char[] data; // 图的节点的字符值
    int[][] weight; // 图的节点的权值

    public Graph(int verxs) {
        this.verxs = verxs;
        this.data = new char[verxs];
        this.weight = new int[verxs][verxs];
    }
}
